package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/16.<br><br>
 *
 * 路径总和 III
 */
public class Topic437 {

    public static void main(String[] args) {
        Topic437 instance = new Topic437();

        List<Integer> list = Arrays.asList(10,5,-3,3,2,null,11,3,-2,null,1);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.pathSum(root, 8));

        list = Arrays.asList(5,4,8,11,null,13,4,7,2,null,null,5,1);
        root = Util.createTree(list);
        System.out.println(instance.pathSum(root, 22));
    }

    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }

        return innerPathSum(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int innerPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }

        return (root.val == targetSum ? 1 : 0) +
                innerPathSum(root.left, targetSum - root.val) + innerPathSum(root.right, targetSum - root.val);
    }
}
